String hashing improvements (spread and performance)
authorMattias Engdegård <mattiase@acm.org>
Tue, 13 Feb 2024 13:52:39 +0000 (14:52 +0100)
committerMattias Engdegård <mattiase@acm.org>
Wed, 14 Feb 2024 13:29:54 +0000 (14:29 +0100)
commit3a93e301ddc913758abe05c876aa3016e8b23af8
tree60e17da4c915a15af930efe1c7fc0bc8532d58fb
parentdecfdd4f1a1e3b1539eafdaaf11191e8477f0636
String hashing improvements (spread and performance)

Fix gaps in hashing coverage in the middle and end of even fairly short
strings.  E.g., `outline-1`, `outline-2` etc all hashed to the exact
same value but with the patch, there are no collisions among the ~160000
symbols in the Emacs tree.

This change also improves average hashing speed by using fewer mixing
operations.

* src/fns.c (hash_string):
Use unit stride for fairly short strings, while retaining the cap of 8
samples for long ones.

Always hash the last word to ensure that the end of the string is
covered.  For strings shorter than a word, use fewer loads and a single
reduction step.
src/fns.c